package zsd.question;

import java.util.ArrayList;
import java.util.List;

import com.aliasi.corpus.ListCorpus;

/**
 * @Title: Test.java
 * @Package zsd.question
 * @Description: TODO(添加描述)
 * @author 朱圣代
 * @date 2011-11-7 下午02:45:04
 * @version V1.0
 */
public class Test {

	/**
	 * @Title: main
	 * @Description:
	 * @param @param args
	 * @return void
	 * @throws
	 * @date 2011-11-7 下午02:45:04
	 * 
	 * 
	 */

	/*
	 * 将一个自然数拆成几个连续的整数的和，比如15可以拆成如下形式
	 * 
	 * 15
	 * 
	 * 7 + 8
	 * 
	 * 4 + 5 + 6
	 * 
	 * 1 + 2 + 3 + 4 + 5
	 */

	// 时间复杂度O(N)
	public static void sequeNumSum(int N) {
		int len = (int) (Math.sqrt(N * 2 + 9.4) - 0.5);
		int start = 1;
		// int firstStart = 1;
		int maxStart = N >> 2;
		for (; len >= 2; len--) {
			for (; start <= N / 2; start++) {
				int sum = (start * 2 + len - 1) * len / 2;
				if (sum == N) {
					int end = start + len;
					for (int k = start; k < end; k++)
						System.out.print(k + " ");
					System.out.println();
					start += 2;
					// firstStart = start;
					break;
				} else if (sum > N) {
					// firstStart = start;
					break;
				}
			}
		}

	}

	// 2分查找
	public static void Aiequali(int[] a, int len) {
		int left = 0;
		int right = len - 1;
		while (left < right - 1) {
			int mid = left + (right - left) / 2;
			if (a[mid] > mid)
				right = mid;
			else {
				left = mid;
			}
		}
		System.out.println(a[left] == left ? left : null);
	}

	/*
	 * 一个整数数列，元素取值可能是0~65535中的任意一个数，相同数值不会重复出现；0是例外，可以反复出现。
	 * 
	 * 请设计一个算法，当你从该数列中随意选取5个数值，判断这5个数值是否连续相邻
	 * 
	 * 注意： ■5个数值允许是乱序的。比如： 8 7 5 0 6 ■0可以通配任意数值。比如：8 7 5 0 6 中的0可以通配成9或者4
	 * ■0可以多次出现。 ■复杂度如果是O(n2)则不得分。
	 */

	// 二叉树的按层次遍历
	static class BTreeNode {
		BTreeNode leftChild;
		BTreeNode rightChild;
		int num;
	}

	public void vistBtreeByLevel(BTreeNode root) {
		List<BTreeNode> nodes = new ArrayList<BTreeNode>();
		nodes.add(root);
		int cur = 0;
		int last = 1;
		BTreeNode curNode;
		int prelast = 0;
		while (prelast < last) {
			curNode = nodes.get(cur);
			System.out.print(curNode.num);
			if (curNode.leftChild != null)
				nodes.add(curNode.leftChild);
			if (curNode.rightChild != null)
				nodes.add(curNode.rightChild);
			cur++;

			if (cur == last) {
				System.out.print("\n");
				prelast = last;
				last = nodes.size();
			}
		}
	}

	// 遍历莫一层的节点,根节点level = 0
	public void visitNode(BTreeNode root, int level) {

	}

	public static void main(String[] args) {
		// Test.sequeNumSum(70000);
		int[] a = { -1, 1, 3, 4, 5 };
		Aiequali(a, 5);
	}

}
